Planar point sets determine many pairwise crossing segments

Abstract: What is the largest number $f(n)$ such that $n$ points in the plane (no three on a line) always determine $f(n)$ pairwise crossing segments. This natural question was asked by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman in 1991 and they proved $f(n)=\Omega(\sqrt{n})$. The prevailing conjecture was that this bound is far from optimal and $f(n)$ is probably linear in $n$. Nevertheless, this lower bound was not improved till last year, when we proved with János Pach and Natan Rubin an almost (but not quite) linear lower bound. Our result gives $f(n)>n/\exp(O(\sqrt{\log n}))$. Determining whether $f(n)$ is truly linear is an intriguing open problem.

combinatoricsprobability

Audience: researchers in the topic

Comments: Password: the first 6 prime numbers (8 digits in total)

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).